package problem;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class S_103 {
    //二叉树的锯齿形层次遍历
      public class TreeNode {
          int val;
          TreeNode left;
          TreeNode right;
          TreeNode(int x) { val = x; }
      }
    //BFS
    class Solution1 {
        public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
            List<List<Integer>> res=new ArrayList<>();
            if(root==null) return res;
            Deque<TreeNode> queue=new LinkedList<>();
            queue.add(root);
            int depth=0;
            while(!queue.isEmpty()){
                List<Integer> tmp=new LinkedList<>();
                int cnt=queue.size();
                //遍历每一层，cnt是每一层的节点数
                for(int i=0;i<cnt;i++){
                    TreeNode node=queue.poll(); //获取队首元素，获取每一层的结点
                    if(depth%2==0) tmp.add(node.val);
                    else tmp.add(0,node.val);
                    if(node.left!=null) queue.add(node.left);
                    if(node.right!=null) queue.add(node.right);
                }
                res.add(tmp);
                depth++;
            }
            return res;
        }
    }
    //DFS
    class Solution2{
        public List<List<Integer>> zigzagLevelOrder(TreeNode root){
            List<List<Integer>> res=new ArrayList<>();
            helper(res,root,0);
            return res;
        }
        private void helper(List<List<Integer>> res,TreeNode root,int depth){
            if(root==null) return;
            //每一层分配一个新数组
            if(res.size()==depth) res.add(new LinkedList<>());
            if(depth%2==0) res.get(depth).add(root.val);
            else res.get(depth).add(0,root.val);
            helper(res,root.left,depth+1);
            helper(res,root.right,depth+1);
        }
    }
}
